package de.pass.ch.dijkstra;

import de.pass.ch.datastr.BinaryHeap;
import de.pass.ch.datastr.IntArrayGrowable;
import de.pass.ch.datastr.PQueueNodeLocalSearch;
import de.pass.ch.graph.UpdateableGraph;
import de.pass.ch.graph.edge.Edge;
import de.pass.ch.graph.node.CurrentNode;
import de.pass.ch.graph.node.INode;
import de.pass.ch.util.Constants;

public class LocalDijkstraContract extends
		AbstractDijkstra<PQueueNodeLocalSearch> {

	@SuppressWarnings("unchecked")
	public LocalDijkstraContract(UpdateableGraph graph) {

		super(graph, new IntArrayGrowable[2], new BinaryHeap[2]);

		_settledNodes[0] = new IntArrayGrowable(100);
		_settledNodes[1] = null;

		_pqueue[0] = new BinaryHeap<PQueueNodeLocalSearch>(500,
				new PQueueNodeLocalSearch());
		_pqueue[1] = null;

		_searchDirections = 1;

	}

	/**
	 * Unidirectional search from a given node s. Used by the construction and
	 * the normal version of Dijkstra's algorithm.
	 * 
	 * @param s
	 *            source node
	 * 
	 *            The following parameters are only for local searches, template
	 *            parameter localSearch enabled:
	 * @param ignore
	 *            ignore this node during the search (do not relax edges to this
	 *            node)
	 * @param maxKey
	 *            stop the search if the smallest tentative distance in the
	 *            pqueue is larger than this limit. (only for localSearch)
	 * @param noOfTargets
	 *            stop the search if this number of nodes with target-flag (in
	 *            the graph) have been settled. (only for localSearch)
	 * @param maxSettled
	 *            stop the search if this number of nodes is settled. 0 =
	 *            disabled (only for localSearch)
	 * @param maxHops
	 *            do only find paths with this number of hops. Template
	 *            parameter countHops needs to be enabled. 0 = disabled (only
	 *            for localSearch)
	 */
	public void searchWithoutTarget(int s, int ignore, int maxKey,
			int noOfTargets, int maxSettled, int maxHops) {

		maxKey = Math.max(maxKey, 0);
		noOfTargets = Math.max(noOfTargets, 0);
		maxSettled = Math.max(maxSettled, 0);
		maxHops = Math.max(maxHops, 0);
		if (ignore < 0)
			ignore = Constants.SPECIAL_NODEID;

		assert (checkClean());

		insertStartNode(s);
		CurrentNode u = new CurrentNode();

		int targetsRemaining = noOfTargets;
		int remaining = maxSettled;
		while (!_pqueue[0].empty()) {
			// *** deleteMin ***
			deleteMin(0, u);

			// a local search is limited
			// abort local search if distance too far
			if (u.dist > maxKey)
				break;

			// search until all targets reached
			if (pqData(0, u.index).isTarget()) {
				targetsRemaining--;
				if (targetsRemaining == 0)
					break;
			}

			// only consider limited settled nodes, then stop search
			remaining--;
			if (remaining == 0)
				break;

			assert (maxHops == 0 || u.hops <= maxHops);
			assert (u.nodeID == s || u.hops > 0);
			// do not relax edges after reaching maxHops count
			if (maxHops > 0 && u.hops >= maxHops)
				continue;

			// *** relaxEdges ***
			relaxEdges(u, ignore);

		}
	}

	/**
	 * Returns the index of the corresponding pq element if the specified node
	 * is settled; returns 0, otherwise.
	 */
	public int isSettled(int vID) {
		int index = _graph.node(vID).getPQElement();
		if (index == 0)
			return 0;
		if (_pqueue[0].isDummy(index))
			return 0;

		// node IS reached ! Is it settled ?
		if (_pqueue[0].elementAt(index).hasBeenDeleted())
			return index;
		return 0;
	}

	/**
	 * Returns the distance from the source node s of the search that has been
	 * performed last to the given node t.
	 * 
	 * @param t
	 *            the target node
	 * @param t
	 *            the search direction that should be considered; special value
	 *            -1 is used to indicate that the result of a bidirectional
	 *            search should be returned
	 * @return distance from s to t or "infinity" if s and t aren't connected
	 */
	public int distanceTo(int t) {
		// special case: return result of the bidirectional search
		if (t == -1)
			return Integer.MAX_VALUE;

		int index = isReached(0, t);
		if (index != 0) {
			return pqKey(0, index);
		} else {
			return Integer.MAX_VALUE; // "infinity" if not connected
		}
	}

	/** Returns the node ID of the parent of the given node t. */
	public int parentOf(int t) {
		int index = isReached(0, t);
		assert (index != 0);
		return pqData(0, index).parentNode();
	}

	/** Clears the search in order to be able to start a new search. */
	public void clear() {

		processUnsettledNodes(0);

		clearNodeVector(0, 100);

		_pqueue[0] = new BinaryHeap<PQueueNodeLocalSearch>(500,
				new PQueueNodeLocalSearch());
	}

	/**
	 * Relaxes all (relevant) edges of the given node for the given search
	 * direction.
	 */
	private void relaxEdges(CurrentNode parent, int ignore) {

		if (ignore < 0)
			ignore = Constants.SPECIAL_NODEID;

		int parentDist = parent.dist;

		// first and last edge of the current node in the current level
		int firstEdge = _graph.firstLevelEdge(parent.nodeID);
		int lastEdge = _graph.lastEdge(parent.nodeID);

		for (parent.edgeID = firstEdge; parent.edgeID < lastEdge; parent.edgeID++) {
			Edge edge = _graph.edge(parent.nodeID, parent.edgeID);

			int vID = edge.getTarget();
			INode v = _graph.node(vID);

			int index = 0;

			// local search: if the current edge points to the node to be
			// ignored, ignore it
			if (vID == ignore)
				continue;

			// if the current edge points to the wrong direction, ignore it
			if (!edge.isDirected((byte) 0))
				continue;

			// the new distance from the source of the search to the target of
			// the edge
			int newDist = parentDist + edge.getWeight();

			// perform the pqueue operation (insert or decreaseKey)
			int e;
			index = isReached(0, v);
			if (index == 0) {
				// v has been unreached -> INSERT it
				e = insert(0, newDist, vID, new PQueueNodeLocalSearch());
			} else {
				// v has been reached -> try to DECREASE its KEY
				e = decreaseKey(0, newDist, vID);
			}
			if (e != 0) {
				// if the pqueue operation/the relaxation of the edge was
				// successful
				PQueueNodeLocalSearch data = pqData(0, e);
				// update the parent of the node v
				data.updateParent(parent.nodeID, parent.edgeID);

				data.setHops(parent.hops + 1);
			}
		}
	}

	private void insertStartNode(int nodeID) {
		int index = insert(0, 0, nodeID, new PQueueNodeLocalSearch());
		PQueueNodeLocalSearch data = pqData(0, index);
		data.setStartNode();
	}
}
